<!DOCTYPE html>
<html>
<head>
<meta http-equiv="Content-type" content="text/html;charset=UTF-8" />
<title>Statements and State &middot; Crafting Interpreters</title>

<!-- Tell mobile browsers we're optimized for them and they don't need to crop
     the viewport. -->
<meta name="viewport" content="width=device-width, initial-scale=1"/>
<link rel="stylesheet" type="text/css" href="style.css" />

<!-- Oh, God, Source Code Pro is so beautiful it makes me want to cry. -->
<link href='https://fonts.googleapis.com/css?family=Source+Code+Pro:400|Source+Sans+Pro:300,400,600' rel='stylesheet' type='text/css'>

<link rel="icon" type="image/png" href="image/favicon.png" />
<script src="jquery-3.4.1.min.js"></script>
<script src="script.js"></script>

<!-- Google analytics -->
<script>
  (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
  (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
  m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
  })(window,document,'script','https://www.google-analytics.com/analytics.js','ga');

  ga('create', 'UA-42804721-2', 'auto');
  ga('send', 'pageview');
</script>

</head>
<body id="top">

<!-- <div class="scrim"></div> -->
<nav class="wide">
  <a href="/"><img src="image/logotype-small.png" title="Crafting Interpreters"></a>
  <div class="contents">
<!-- If there is a part, it must be a chapter within a part. -->
<h3><a href="#top">Statements and State<small>8</small></a></h3>

<ul>
    <li><a href="#statements"><small>8.1</small> Statements</a></li>
    <li><a href="#global-variables"><small>8.2</small> Global Variables</a></li>
    <li><a href="#environments"><small>8.3</small> Environments</a></li>
    <li><a href="#assignment"><small>8.4</small> Assignment</a></li>
    <li><a href="#scope"><small>8.5</small> Scope</a></li>
    <li class="divider"></li>
    <li class="end-part"><a href="#challenges">Challenges</a></li>
    <li class="end-part"><a href="#design-note"><small>note</small>Implicit Variable Declaration</a></li>
</ul>


<div class="prev-next">
    <a href="evaluating-expressions.html" title="Evaluating Expressions" class="left">&larr;&nbsp;Previous</a>
    <a href="a-tree-walk-interpreter.html" title="A Tree-Walk Interpreter">&uarr;&nbsp;Up</a>
    <a href="control-flow.html" title="Control Flow" class="right">Next&nbsp;&rarr;</a>
</div>  </div>
</nav>

<nav class="narrow">
<a href="/"><img src="image/logotype-small.png" title="Crafting Interpreters"></a>
<a href="evaluating-expressions.html" title="Evaluating Expressions" class="prev">←</a>
<a href="control-flow.html" title="Control Flow" class="next">→</a>
</nav>

<div class="page">
<div class="nav-wrapper">
<nav class="floating">
  <a href="/"><img src="image/logotype-small.png" title="Crafting Interpreters"></a>
  <div class="expandable">
<!-- If there is a part, it must be a chapter within a part. -->
<h3><a href="#top">Statements and State<small>8</small></a></h3>

<ul>
    <li><a href="#statements"><small>8.1</small> Statements</a></li>
    <li><a href="#global-variables"><small>8.2</small> Global Variables</a></li>
    <li><a href="#environments"><small>8.3</small> Environments</a></li>
    <li><a href="#assignment"><small>8.4</small> Assignment</a></li>
    <li><a href="#scope"><small>8.5</small> Scope</a></li>
    <li class="divider"></li>
    <li class="end-part"><a href="#challenges">Challenges</a></li>
    <li class="end-part"><a href="#design-note"><small>note</small>Implicit Variable Declaration</a></li>
</ul>


<div class="prev-next">
    <a href="evaluating-expressions.html" title="Evaluating Expressions" class="left">&larr;&nbsp;Previous</a>
    <a href="a-tree-walk-interpreter.html" title="A Tree-Walk Interpreter">&uarr;&nbsp;Up</a>
    <a href="control-flow.html" title="Control Flow" class="right">Next&nbsp;&rarr;</a>
</div>  </div>
  <a id="expand-nav">≡</a>
</nav>
</div>

<article class="chapter">

  <div class="number">8</div>
  <h1>Statements and State</h1>

<div class="sign-up closable">
  <h1>This book is a work in progress!</h1>
    <span class="dismiss">&times;</span>
    <p>If you see a mistake, find something unclear, or have a suggestion, please <a href="https://github.com/munificent/craftinginterpreters/issues" target="_blank">let me know</a>. To follow its progress, please join the mailing list:</p>

  <!-- Begin MailChimp Signup Form -->
  <div id="mc_embed_signup">
  <form action="//gameprogrammingpatterns.us7.list-manage.com/subscribe/post?u=0952ca43ed2536d6717766b88&amp;id=6e96334109" method="post" id="mc-embedded-subscribe-form" name="mc-embedded-subscribe-form" class="validate" target="_blank" novalidate>
    <input type="email" value="" name="EMAIL" class="email" id="mce-EMAIL" placeholder="Your email address" required>
    <!-- real people should not fill this in and expect good things - do not remove this or risk form bot signups-->
    <div style="position: absolute; left: -5000px;" aria-hidden="true"><input type="text" name="b_0952ca43ed2536d6717766b88_6e96334109" tabindex="-1" value=""></div>
    <input type="submit" value="Sign me up!" name="subscribe" id="mc-embedded-subscribe" class="button">
  </form>
  </div>
  <!--End mc_embed_signup-->
  <p class="small">(I post about once a month. Don&#8217;t worry, I won&#8217;t spam you.)</p>
</div>

<blockquote>
<p>All my life, my heart has yearned for a thing I cannot name.
<cite>Andre Breton, <em>Mad Love</em></cite></p>
</blockquote>
<p>The interpreter we have so far feels less like programming a real language and
more like punching buttons on a calculator. &ldquo;Programming&rdquo; to me means building
up a system out of smaller pieces. We can&rsquo;t do that yet because we have no way
to bind a name to some data or function. We can&rsquo;t compose software without a way
to refer to the pieces.</p>
<p>To support bindings, our interpreter needs internal state. When you define a
variable at the beginning of the program and use it at the end, the interpreter
has to hold on to the value of that variable in the meantime. So in this
chapter, we will give our interpreter a brain that can not just process, but
<em>remember</em>.</p><img src="image/statements-and-state/brain.png" alt="A brain, presumably remembering stuff." />
<p>State and <span name="expr">statements</span> go hand in hand. Since statements,
by definition, don&rsquo;t evaluate to a value, they need to do something else to be
useful. That something is called a <strong>side effect</strong>. It could mean producing
user-visible output or modifying some state in the interpreter that can be
detected later. The latter makes them a great fit for defining variables or
other named entities.</p>
<aside name="expr">
<p>You could make a language that treats variable declarations as expressions that
both create a binding and produce a value, but I&rsquo;m not aware of any widely-used
languages that do. Scheme seems like a contender, but note that after a <code>let</code>
expression is evaluated, the variable it bound is forgotten. The <code>define</code> syntax
is not an expression.</p>
</aside>
<p>In this chapter, we&rsquo;ll do all of that. We&rsquo;ll define statements that produce
output (<code>print</code>) and create state (<code>var</code>). We&rsquo;ll add expressions to access and
assign to variables. Finally, we&rsquo;ll add blocks and local scope. That&rsquo;s a lot to
stuff into one chapter, but we&rsquo;ll chew through it all one bite at a time.</p>
<h2><a href="#statements" name="statements"><small>8&#8202;.&#8202;1</small>Statements</a></h2>
<p>We start by extending Lox&rsquo;s grammar with statements. They aren&rsquo;t very different
from expressions. We start with the two simplest kinds:</p>
<ol>
<li>
<p>An <strong>expression statement</strong> lets you place an expression where a statement
is expected. They exist to evaluate expressions that have side effects. You
may not notice them, but you use them all the time in <span
name="expr-stmt">C</span>, Java, and other languages. Any time you see a
function or method call followed by a <code>;</code>, you&rsquo;re looking at an expression
statement.</p>
<aside name="expr-stmt">
<p>Pascal is an outlier. It distinguishes between <em>procedures</em> and <em>functions</em>.
Functions return values, but procedures cannot. There is a statement form
for calling a procedure, but functions can only be called where an
expression is expected. There are no expression statements.</p>
</aside></li>
<li>
<p>A <strong><code>print</code> statement</strong> evaluates an expression and displays the result to
the user. I admit it&rsquo;s weird to bake printing right into the language
instead of making it a library function. Doing so is a concession to the
fact that we&rsquo;re building this interpreter one chapter at a time and want to
be able to play with it before it&rsquo;s all done. To make print a library
function, we&rsquo;d have to wait until we had all of the machinery for defining
and calling functions <span name="print">before</span> we could witness any
side effects.</p>
<aside name="print">
<p>I will note with only a modicum of defensiveness that BASIC and Python
have dedicated <code>print</code> statements and they are real languages. Granted,
Python did remove their <code>print</code> statement in 3.0&hellip;</p>
</aside></li>
</ol>
<p>New syntax means new grammar rules. In this chapter, we finally gain the ability
to parse an entire Lox script. Since Lox is an imperative, dynamically-typed
language, the &ldquo;top level&rdquo; of a script is simply a list of statements. The new
rules are:</p>
<div class="codehilite"><pre>
<span class="i">program</span>        → <span class="i">statement</span>* <span class="t">EOF</span> ;

<span class="i">statement</span>      → <span class="i">exprStmt</span>
               | <span class="i">printStmt</span> ;

<span class="i">exprStmt</span>       → <span class="i">expression</span> <span class="s">&quot;;&quot;</span> ;
<span class="i">printStmt</span>      → <span class="s">&quot;print&quot;</span> <span class="i">expression</span> <span class="s">&quot;;&quot;</span> ;
</pre></div>
<p>The first rule is now <code>program</code>, which is the starting point for the grammar and
represents a complete Lox script or REPL entry. A program is a list of
statements followed by the special &ldquo;end of file&rdquo; token. The mandatory end token
ensures the parser consumes the entire input and doesn&rsquo;t silently ignore
erroneous unconsumed tokens at the end of a script.</p>
<p>Right now, <code>statement</code> only has two cases for the two kinds of statements we&rsquo;ve
described. We&rsquo;ll fill in more later in this chapter and in the following ones.
The next step is turning this grammar into something we can store in memory<span class="em">&mdash;</span>syntax trees.</p>
<h3><a href="#statement-syntax-trees" name="statement-syntax-trees"><small>8&#8202;.&#8202;1&#8202;.&#8202;1</small>Statement syntax trees</a></h3>
<p>There is no place in the grammar where both an expression and a statement is
allowed. The operands of, say, <code>+</code> are always expressions, never statements. The
body of a <code>while</code> loop is always a statement.</p>
<p>Since the two syntaxes are disjoint, we don&rsquo;t need a single base class that they
all inherit from. Splitting expressions and statements into separate class
hierarchies enables the Java compiler to help us find dumb mistakes like passing
a statement to a Java method that expects an expression.</p>
<p>That means a new base class for statements. As our elders did before us, we will
use the cryptic name &ldquo;Stmt&rdquo;. With great <span name="foresight">foresight</span>,
I have designed our little AST metaprogramming script in anticipation of this.
That&rsquo;s why we passed in &ldquo;Expr&rdquo; as a parameter to <code>defineAst()</code>. Now we add
another call to define Stmt and its <span name="stmt-ast">subclasses</span>.</p>
<aside name="foresight">
<p>Not really foresight: I wrote all the code for the book before I sliced it into
chapters.</p>
</aside>
<div class="codehilite"><pre class="insert-before">
      &quot;Unary    : Token operator, Expr right&quot;
    ));
</pre><div class="source-file"><em>tool/GenerateAst.java</em><br>
in <em>main</em>()</div>
<pre class="insert">

    <span class="i">defineAst</span>(<span class="i">outputDir</span>, <span class="s">&quot;Stmt&quot;</span>, <span class="t">Arrays</span>.<span class="i">asList</span>(
      <span class="s">&quot;Expression : Expr expression&quot;</span>,
      <span class="s">&quot;Print      : Expr expression&quot;</span>
    ));
</pre><pre class="insert-after">
  }
</pre></div>
<div class="source-file-narrow"><em>tool/GenerateAst.java</em>, in <em>main</em>()</div>

<aside name="stmt-ast">
<p>The generated code for the new nodes is in <a href="appendix-ii.html">Appendix II</a>: <a href="appendix-ii.html#expression-statement">Expression statement</a>, <a href="appendix-ii.html#print-statement">Print statement</a>.</p>
</aside>
<p>Run the AST generator script and behold the resulting &ldquo;Stmt.java&rdquo; file with the
syntax tree classes we need for expression and <code>print</code> statements. Don&rsquo;t forget
to add the file to your IDE project or makefile or whatever.</p>
<h3><a href="#parsing-statements" name="parsing-statements"><small>8&#8202;.&#8202;1&#8202;.&#8202;2</small>Parsing statements</a></h3>
<p>The parser&rsquo;s <code>parse()</code> method that parses and returns a single expression was a
temporary hack to get the last chapter up and running. Now that our grammar has
the correct starting rule, <code>program</code>, we can turn <code>parse()</code> into the real deal.</p>
<div class="codehilite"><div class="source-file"><em>lox/Parser.java</em><br>
method <em>parse</em>()<br>
replace 7 lines</div>
<pre>
  <span class="t">List</span>&lt;<span class="t">Stmt</span>&gt; <span class="i">parse</span>() {
    <span class="t">List</span>&lt;<span class="t">Stmt</span>&gt; <span class="i">statements</span> = <span class="k">new</span> <span class="t">ArrayList</span>&lt;&gt;();
    <span class="k">while</span> (!<span class="i">isAtEnd</span>()) {
      <span class="i">statements</span>.<span class="i">add</span>(<span class="i">statement</span>());
    }

    <span class="k">return</span> <span class="i">statements</span>;<span name="parse-error-handling"> </span>
  }
</pre></div>
<div class="source-file-narrow"><em>lox/Parser.java</em>, method <em>parse</em>(), replace 7 lines</div>

<aside name="parse-error-handling">
<p>What about the code we had in here for catching <code>ParseError</code> exceptions? We&rsquo;ll
put better parse error handling in place soon when we add support for additional
statement types.</p>
</aside>
<p>This parses a series of statements, as many as it can find until it hits the end
of the input. This is a pretty direct translation of the <code>program</code> rule into
recursive descent style. We must also chant a minor prayer to the Java Verbosity
Gods since we are using ArrayList now.</p>
<div class="codehilite"><pre class="insert-before">
package com.craftinginterpreters.lox;

</pre><div class="source-file"><em>lox/Parser.java</em></div>
<pre class="insert">
<span class="k">import</span> <span class="i">java.util.ArrayList</span>;
</pre><pre class="insert-after">
import java.util.List;
</pre></div>
<div class="source-file-narrow"><em>lox/Parser.java</em></div>

<p>A program is a list of statements, and we parse one of those statements using
this method:</p>
<div class="codehilite"><div class="source-file"><em>lox/Parser.java</em><br>
add after <em>expression</em>()</div>
<pre>
  <span class="k">private</span> <span class="t">Stmt</span> <span class="i">statement</span>() {
    <span class="k">if</span> (<span class="i">match</span>(<span class="i">PRINT</span>)) <span class="k">return</span> <span class="i">printStatement</span>();

    <span class="k">return</span> <span class="i">expressionStatement</span>();
  }
</pre></div>
<div class="source-file-narrow"><em>lox/Parser.java</em>, add after <em>expression</em>()</div>

<p>A little bare bones, but we&rsquo;ll fill it in with more statement types later. We
determine which specific statement rule is matched by looking at the current
token. A <code>print</code> token means it&rsquo;s obviously a <code>print</code> statement.</p>
<p>If the next token doesn&rsquo;t look like any known kind of statement, we assume it
must be an expression statement. That&rsquo;s the typical final fallthrough case when
parsing a statement, since it&rsquo;s hard to proactively recognize an expression from
its first token.</p>
<p>Each statement kind gets its own method. First print:</p>
<div class="codehilite"><div class="source-file"><em>lox/Parser.java</em><br>
add after <em>statement</em>()</div>
<pre>
  <span class="k">private</span> <span class="t">Stmt</span> <span class="i">printStatement</span>() {
    <span class="t">Expr</span> <span class="i">value</span> = <span class="i">expression</span>();
    <span class="i">consume</span>(<span class="i">SEMICOLON</span>, <span class="s">&quot;Expect &#39;;&#39; after value.&quot;</span>);
    <span class="k">return</span> <span class="k">new</span> <span class="t">Stmt</span>.<span class="t">Print</span>(<span class="i">value</span>);
  }
</pre></div>
<div class="source-file-narrow"><em>lox/Parser.java</em>, add after <em>statement</em>()</div>

<p>Since we already matched and consumed the <code>print</code> token itself, we don&rsquo;t need to
do that here. We parse the subsequent expression, consume the terminating
semicolon, and emit the syntax tree.</p>
<p>If we didn&rsquo;t match a <code>print</code> statement, we must have one of these:</p>
<div class="codehilite"><div class="source-file"><em>lox/Parser.java</em><br>
add after <em>printStatement</em>()</div>
<pre>
  <span class="k">private</span> <span class="t">Stmt</span> <span class="i">expressionStatement</span>() {
    <span class="t">Expr</span> <span class="i">expr</span> = <span class="i">expression</span>();
    <span class="i">consume</span>(<span class="i">SEMICOLON</span>, <span class="s">&quot;Expect &#39;;&#39; after expression.&quot;</span>);
    <span class="k">return</span> <span class="k">new</span> <span class="t">Stmt</span>.<span class="t">Expression</span>(<span class="i">expr</span>);
  }
</pre></div>
<div class="source-file-narrow"><em>lox/Parser.java</em>, add after <em>printStatement</em>()</div>

<p>Similar to the previous method, we parse an expression followed by a semicolon.
We wrap that Expr in a Stmt of the right type and return it.</p>
<h3><a href="#executing-statements" name="executing-statements"><small>8&#8202;.&#8202;1&#8202;.&#8202;3</small>Executing statements</a></h3>
<p>We&rsquo;re running through the previous couple of chapters in microcosm, working our
way through the front end. Our parser can now produce statement syntax trees, so
the next and final step is to interpret them. As in expressions, we use the
Visitor pattern, but we have a new visitor interface, Stmt.Visitor, to
implement since statements have their own base class.</p>
<p>We add that to the list of interfaces Interpreter implements.</p>
<div class="codehilite"><div class="source-file"><em>lox/Interpreter.java</em><br>
replace 1 line</div>
<pre class="insert">
<span class="k">class</span> <span class="t">Interpreter</span> <span class="k">implements</span> <span class="t">Expr</span>.<span class="t">Visitor</span>&lt;<span class="t">Object</span>&gt;,
                             <span class="t">Stmt</span>.<span class="t">Visitor</span>&lt;<span class="t">Void</span>&gt; {
</pre><pre class="insert-after">
  void interpret(Expr expression) {<span name="void"> </span>
</pre></div>
<div class="source-file-narrow"><em>lox/Interpreter.java</em>, replace 1 line</div>

<aside name="void">
<p>Java doesn&rsquo;t let you use lowercase &ldquo;void&rdquo; as a generic type argument for obscure
reasons having to do with type erasure and the stack. Instead, there is a
separate &ldquo;Void&rdquo; type specifically for this use. Sort of a &ldquo;boxed void&rdquo;, like
&ldquo;Integer&rdquo; is for &ldquo;int&rdquo;.</p>
</aside>
<p>Unlike expressions, statements produce no values, so the return type of the
visit methods is Void, not Object. We have two statement types, and we need a
visit method for each. The easiest is expression statements.</p>
<div class="codehilite"><div class="source-file"><em>lox/Interpreter.java</em><br>
add after <em>evaluate</em>()</div>
<pre>
  <span class="a">@Override</span>
  <span class="k">public</span> <span class="t">Void</span> <span class="i">visitExpressionStmt</span>(<span class="t">Stmt</span>.<span class="t">Expression</span> <span class="i">stmt</span>) {
    <span class="i">evaluate</span>(<span class="i">stmt</span>.<span class="i">expression</span>);
    <span class="k">return</span> <span class="k">null</span>;
  }
</pre></div>
<div class="source-file-narrow"><em>lox/Interpreter.java</em>, add after <em>evaluate</em>()</div>

<p>We evaluate the inner expression using our existing <code>evaluate()</code> method and
<span name="discard">discard</span> the value. Then we return <code>null</code>. Java
requires that to satisfy the special capitalized Void return type. Weird, but
what can you do?</p>
<aside name="discard">
<p>Appropriately enough, we discard the value returned by <code>evaluate()</code> by placing
that call inside a <em>Java</em> expression statement.</p>
</aside>
<p>The <code>print</code> statement&rsquo;s visit method isn&rsquo;t much different.</p>
<div class="codehilite"><div class="source-file"><em>lox/Interpreter.java</em><br>
add after <em>visitExpressionStmt</em>()</div>
<pre>
  <span class="a">@Override</span>
  <span class="k">public</span> <span class="t">Void</span> <span class="i">visitPrintStmt</span>(<span class="t">Stmt</span>.<span class="t">Print</span> <span class="i">stmt</span>) {
    <span class="t">Object</span> <span class="i">value</span> = <span class="i">evaluate</span>(<span class="i">stmt</span>.<span class="i">expression</span>);
    <span class="t">System</span>.<span class="i">out</span>.<span class="i">println</span>(<span class="i">stringify</span>(<span class="i">value</span>));
    <span class="k">return</span> <span class="k">null</span>;
  }
</pre></div>
<div class="source-file-narrow"><em>lox/Interpreter.java</em>, add after <em>visitExpressionStmt</em>()</div>

<p>Before discarding the expression&rsquo;s value, we convert it to a string using the
<code>stringify()</code> method we introduced in the last chapter and then dump it to
stdout.</p>
<p>Our interpreter is able to visit statements now, but we have some work to do to
feed them to it. First, modify the old <code>interpret()</code> method in the Interpreter
class to accept a list of statements<span class="em">&mdash;</span>in other words, a program.</p>
<div class="codehilite"><div class="source-file"><em>lox/Interpreter.java</em><br>
method <em>interpret</em>()<br>
replace 8 lines</div>
<pre>
  <span class="t">void</span> <span class="i">interpret</span>(<span class="t">List</span>&lt;<span class="t">Stmt</span>&gt; <span class="i">statements</span>) {
    <span class="k">try</span> {
      <span class="k">for</span> (<span class="t">Stmt</span> <span class="i">statement</span> : <span class="i">statements</span>) {
        <span class="i">execute</span>(<span class="i">statement</span>);
      }
    } <span class="k">catch</span> (<span class="t">RuntimeError</span> <span class="i">error</span>) {
      <span class="t">Lox</span>.<span class="i">runtimeError</span>(<span class="i">error</span>);
    }
  }
</pre></div>
<div class="source-file-narrow"><em>lox/Interpreter.java</em>, method <em>interpret</em>(), replace 8 lines</div>

<p>This replaces the old code which took a single expression. The new code relies
on this tiny helper method:</p>
<div class="codehilite"><div class="source-file"><em>lox/Interpreter.java</em><br>
add after <em>evaluate</em>()</div>
<pre>
  <span class="k">private</span> <span class="t">void</span> <span class="i">execute</span>(<span class="t">Stmt</span> <span class="i">stmt</span>) {
    <span class="i">stmt</span>.<span class="i">accept</span>(<span class="k">this</span>);
  }
</pre></div>
<div class="source-file-narrow"><em>lox/Interpreter.java</em>, add after <em>evaluate</em>()</div>

<p>That&rsquo;s the statement analogue to the <code>evaluate()</code> method we have for
expressions. Since we&rsquo;re working with lists now, we need to let Java know.</p>
<div class="codehilite"><pre class="insert-before">
package com.craftinginterpreters.lox;
</pre><div class="source-file"><em>lox/Interpreter.java</em></div>
<pre class="insert">

<span class="k">import</span> <span class="i">java.util.List</span>;
</pre><pre class="insert-after">

class Interpreter implements Expr.Visitor&lt;Object&gt;,
</pre></div>
<div class="source-file-narrow"><em>lox/Interpreter.java</em></div>

<p>The main Lox class is still trying to parse a single expression and pass it to
the interpreter. We fix the parsing line like so:</p>
<div class="codehilite"><pre class="insert-before">
    Parser parser = new Parser(tokens);
</pre><div class="source-file"><em>lox/Lox.java</em><br>
in <em>run</em>()<br>
replace 1 line</div>
<pre class="insert">
    <span class="t">List</span>&lt;<span class="t">Stmt</span>&gt; <span class="i">statements</span> = <span class="i">parser</span>.<span class="i">parse</span>();
</pre><pre class="insert-after">

    // Stop if there was a syntax error.
</pre></div>
<div class="source-file-narrow"><em>lox/Lox.java</em>, in <em>run</em>(), replace 1 line</div>

<p>And then replace the call to the interpreter with this:</p>
<div class="codehilite"><pre class="insert-before">
    if (hadError) return;

</pre><div class="source-file"><em>lox/Lox.java</em><br>
in <em>run</em>()<br>
replace 1 line</div>
<pre class="insert">
    <span class="i">interpreter</span>.<span class="i">interpret</span>(<span class="i">statements</span>);
</pre><pre class="insert-after">
  }
</pre></div>
<div class="source-file-narrow"><em>lox/Lox.java</em>, in <em>run</em>(), replace 1 line</div>

<p>Basically just plumbing the new syntax through. OK, fire up the interpreter and
give it a try. At this point, it&rsquo;s worth sketching out a little Lox program in a
text file to run as a script. Something like:</p>
<div class="codehilite"><pre>
<span class="k">print</span> <span class="s">&quot;one&quot;</span>;
<span class="k">print</span> <span class="k">true</span>;
<span class="k">print</span> <span class="n">2</span> + <span class="n">1</span>;
</pre></div>
<p>It almost looks like a real program! Note that the REPL too now requires you to
enter a full statement instead of a simple expression. Don&rsquo;t forget your
semicolons.</p>
<h2><a href="#global-variables" name="global-variables"><small>8&#8202;.&#8202;2</small>Global Variables</a></h2>
<p>Now that we have statements, we can start working on state. Before we get into
all of the complexity of lexical scoping, we&rsquo;ll start off with the easiest kind
of variables<span class="em">&mdash;</span><span name="globals">globals</span>. We need two new constructs.</p>
<ol>
<li>
<p>A <strong>variable declaration</strong> statement brings a new variable into the world:</p>
<div class="codehilite"><pre>
<span class="k">var</span> <span class="i">beverage</span> = <span class="s">&quot;espresso&quot;</span>;
</pre></div>
<p>This creates a new binding that associates a name (here &ldquo;beverage&rdquo;) with a
value (here, the string <code>"espresso"</code>).</p>
</li>
<li>
<p>Once that&rsquo;s done, a <strong>variable expression</strong> accesses that binding. When the
identifier &ldquo;beverage&rdquo; is used as an expression, it looks up the value bound
to that name and returns it:</p>
<div class="codehilite"><pre>
<span class="k">print</span> <span class="i">beverage</span>; <span class="c">// &quot;espresso&quot;.</span>
</pre></div>
</li>
</ol>
<p>Later, we&rsquo;ll add assignment and block scope, but that&rsquo;s enough to get moving.</p>
<aside name="globals">
<p>Global state gets a bad rap. Sure, lots of global state<span class="em">&mdash;</span>especially <em>mutable</em>
state<span class="em">&mdash;</span>makes it hard to maintain large programs. It&rsquo;s good software
engineering to minimize how much you use.</p>
<p>But when you&rsquo;re slapping together a simple programming language or, heck, even
learning your first language, the flat simplicity of global variables helps. My
first language was BASIC and, though I outgrew it eventually, it was nice that I
didn&rsquo;t have to wrap my head around scoping rules before I could make a computer
do fun stuff.</p>
</aside>
<h3><a href="#variable-syntax" name="variable-syntax"><small>8&#8202;.&#8202;2&#8202;.&#8202;1</small>Variable syntax</a></h3>
<p>As before, we&rsquo;ll work through the implementation from front to back, starting
with the syntax. Variable declarations are statements, but they are different
from other statements, and we&rsquo;re going to split the statement grammar in two to
handle them. That&rsquo;s because the grammar restricts where some kinds of statements
are allowed.</p>
<p>The clauses in control flow statements<span class="em">&mdash;</span>think the then and else branches of
an <code>if</code> statement or the body of a <code>while</code><span class="em">&mdash;</span>are each a single statement. But
that statement is not allowed to be one that declares a name. This is OK:</p>
<div class="codehilite"><pre>
<span class="k">if</span> (<span class="i">monday</span>) <span class="k">print</span> <span class="s">&quot;Ugh, already?&quot;</span>;
</pre></div>
<p>But this is not:</p>
<div class="codehilite"><pre>
<span class="k">if</span> (<span class="i">monday</span>) <span class="k">var</span> <span class="i">beverage</span> = <span class="s">&quot;espresso&quot;</span>;
</pre></div>
<p>We <em>could</em> allow the latter, but it&rsquo;s confusing. What is the scope of that
<code>beverage</code> variable? Does it persist after the <code>if</code> statement? If so, what is
its value on days other than Monday? Does the variable exist at all on those
days?</p>
<p>Code like this is weird, so C, Java, and friends all disallow it. It&rsquo;s as if
there are two levels of <span name="brace">&ldquo;precedence&rdquo;</span> for statements.
Some places where a statement is allowed<span class="em">&mdash;</span>like inside a block or at the top
level<span class="em">&mdash;</span>allow any kind of statement, including declarations. Others only allow
the &ldquo;higher&rdquo; precedence statements that don&rsquo;t declare names.</p>
<aside name="brace">
<p>In this analogy, a block statement, where you stuff a series of statements
inside a pair of curly braces, works sort of like parentheses for expressions. A
block statement is itself in the &ldquo;higher&rdquo; precedence level and can be used
anywhere, like in the clauses of an <code>if</code> statement. But the statements it
<em>contains</em> can be lower precedence. You&rsquo;re allowed to declare variables and
other names inside the block. The curlies let you escape back into the full
statement grammar from a place where only some statements are allowed.</p>
</aside>
<p>To accommodate the distinction, we add another rule for kinds of statements that
declare names.</p>
<div class="codehilite"><pre>
<span class="i">program</span>        → <span class="i">declaration</span>* <span class="t">EOF</span> ;

<span class="i">declaration</span>    → <span class="i">varDecl</span>
               | <span class="i">statement</span> ;

<span class="i">statement</span>      → <span class="i">exprStmt</span>
               | <span class="i">printStmt</span> ;
</pre></div>
<p>Declaration statements go under the new <code>declaration</code> rule. Right now, it&rsquo;s only
variables, but later it will include functions and classes. Any place where a
declaration is allowed also allows non-declaring statements, so the
<code>declaration</code> rule falls through to <code>statement</code>. Obviously, you can declare
stuff at the top level of a script, so <code>program</code> routes to the new rule.</p>
<p>The rule for declaring a variable looks like:</p>
<div class="codehilite"><pre>
<span class="i">varDecl</span>        → <span class="s">&quot;var&quot;</span> <span class="t">IDENTIFIER</span> ( <span class="s">&quot;=&quot;</span> <span class="i">expression</span> )? <span class="s">&quot;;&quot;</span> ;
</pre></div>
<p>Like most statements, it starts with a leading keyword. In this case, <code>var</code>.
Then an identifier token for the name of the variable being declared, followed
by an optional initializer expression. Finally, we put a bow on it with the
semicolon.</p>
<p>To access a variable, we define a new kind of primary expression:</p>
<div class="codehilite"><pre>
<span class="i">primary</span>        → <span class="s">&quot;true&quot;</span> | <span class="s">&quot;false&quot;</span> | <span class="s">&quot;nil&quot;</span>
               | <span class="t">NUMBER</span> | <span class="t">STRING</span>
               | <span class="s">&quot;(&quot;</span> <span class="i">expression</span> <span class="s">&quot;)&quot;</span>
               | <span class="t">IDENTIFIER</span> ;
</pre></div>
<p>That <code>IDENTIFIER</code> clause matches a single identifier token, which is understood
to be the name of the variable being accessed.</p>
<p>These new grammar rules get their corresponding syntax trees. Over in the AST
generator, we add a <span name="var-stmt-ast">new statement</span> tree for a
variable declaration:</p>
<div class="codehilite"><pre class="insert-before">
      &quot;Expression : Expr expression&quot;,
</pre><pre class="insert-before">
      <span class="s">&quot;Print      : Expr expression&quot;</span><span class="insert-comma">,</span>
</pre><div class="source-file"><em>tool/GenerateAst.java</em><br>
in <em>main</em>()<br>
add <em>&ldquo;,&rdquo;</em> to previous line</div>
<pre class="insert">
      <span class="s">&quot;Var        : Token name, Expr initializer&quot;</span>
</pre><pre class="insert-after">
    ));
</pre></div>
<div class="source-file-narrow"><em>tool/GenerateAst.java</em>, in <em>main</em>(), add <em>&ldquo;,&rdquo;</em> to previous line</div>

<aside name="var-stmt-ast">
<p>The generated code for the new node is in <a href="appendix-ii.html#variable-statement">Appendix II</a>.</p>
</aside>
<p>It stores the name token so we know what it&rsquo;s declaring, along with the
initializer expression. (If there isn&rsquo;t an initializer, that field is <code>null</code>.)</p>
<p>Then we add an expression node for accessing a variable:</p>
<div class="codehilite"><pre class="insert-before">
      &quot;Literal  : Object value&quot;,
</pre><pre class="insert-before">
      <span class="s">&quot;Unary    : Token operator, Expr right&quot;</span><span class="insert-comma">,</span>
</pre><div class="source-file"><em>tool/GenerateAst.java</em><br>
in <em>main</em>()<br>
add <em>&ldquo;,&rdquo;</em> to previous line</div>
<pre class="insert">
      <span class="s">&quot;Variable : Token name&quot;</span>
</pre><pre class="insert-after">
    ));
</pre></div>
<div class="source-file-narrow"><em>tool/GenerateAst.java</em>, in <em>main</em>(), add <em>&ldquo;,&rdquo;</em> to previous line</div>

<p><span name="var-expr-ast">It&rsquo;s</span> simply a wrapper around the token for the
variable name. That&rsquo;s it. As always, don&rsquo;t forget to run the AST generator
script so that you get updated &ldquo;Expr.java&rdquo; and &ldquo;Stmt.java&rdquo; files.</p>
<aside name="var-expr-ast">
<p>The generated code for the new node is in <a href="appendix-ii.html#variable-expression">Appendix II</a>.</p>
</aside>
<h3><a href="#parsing-variables" name="parsing-variables"><small>8&#8202;.&#8202;2&#8202;.&#8202;2</small>Parsing variables</a></h3>
<p>Before we parse variable statements, we need to shift around some code to make
room for the new <code>declaration</code> rule in the grammar. The top level of a program
is now a list of declarations, so the entrypoint method to the parser changes.</p>
<div class="codehilite"><pre class="insert-before">
  List&lt;Stmt&gt; parse() {
    List&lt;Stmt&gt; statements = new ArrayList&lt;&gt;();
    while (!isAtEnd()) {
</pre><div class="source-file"><em>lox/Parser.java</em><br>
in <em>parse</em>()<br>
replace 1 line</div>
<pre class="insert">
      <span class="i">statements</span>.<span class="i">add</span>(<span class="i">declaration</span>());
</pre><pre class="insert-after">
    }

    return statements;<span name="parse-error-handling"> </span>
  }
</pre></div>
<div class="source-file-narrow"><em>lox/Parser.java</em>, in <em>parse</em>(), replace 1 line</div>

<p>That calls this new method:</p>
<div class="codehilite"><div class="source-file"><em>lox/Parser.java</em><br>
add after <em>expression</em>()</div>
<pre>
  <span class="k">private</span> <span class="t">Stmt</span> <span class="i">declaration</span>() {
    <span class="k">try</span> {
      <span class="k">if</span> (<span class="i">match</span>(<span class="i">VAR</span>)) <span class="k">return</span> <span class="i">varDeclaration</span>();

      <span class="k">return</span> <span class="i">statement</span>();
    } <span class="k">catch</span> (<span class="t">ParseError</span> <span class="i">error</span>) {
      <span class="i">synchronize</span>();
      <span class="k">return</span> <span class="k">null</span>;
    }
  }
</pre></div>
<div class="source-file-narrow"><em>lox/Parser.java</em>, add after <em>expression</em>()</div>

<p>Hey, do you remember way back in that <a href="parsing-expressions.html">earlier chapter</a> when we put the
infrastructure in place to do error recovery? We are finally ready to hook that
up.</p>
<p>This <code>declaration()</code> method is the method we call repeatedly when parsing a
series of statements in a block or a script, so it&rsquo;s the right place to
synchronize when the parser goes into panic mode. The whole body of this method
is wrapped in a try block to catch the exception thrown when the parser begins
error recovery. This gets it back to trying to parse the beginning of the next
statement or declaration.</p>
<p>The real parsing happens inside the try block. First, it looks to see if we&rsquo;re
at a variable declaration by looking for the leading <code>var</code> keyword. If not, it
falls through to the existing <code>statement()</code> method that parses <code>print</code> and
expression statements.</p>
<p>Remember how <code>statement()</code> tries to parse an expression statement if no other
statement matches? And <code>expression()</code> reports a syntax error if it can&rsquo;t parse
an expression at the current token? That chain of calls ensures we report an
error if a valid declaration or statement isn&rsquo;t parsed.</p>
<p>When the parser matches a <code>var</code> token, it branches to:</p>
<div class="codehilite"><div class="source-file"><em>lox/Parser.java</em><br>
add after <em>printStatement</em>()</div>
<pre>
  <span class="k">private</span> <span class="t">Stmt</span> <span class="i">varDeclaration</span>() {
    <span class="t">Token</span> <span class="i">name</span> = <span class="i">consume</span>(<span class="i">IDENTIFIER</span>, <span class="s">&quot;Expect variable name.&quot;</span>);

    <span class="t">Expr</span> <span class="i">initializer</span> = <span class="k">null</span>;
    <span class="k">if</span> (<span class="i">match</span>(<span class="i">EQUAL</span>)) {
      <span class="i">initializer</span> = <span class="i">expression</span>();
    }

    <span class="i">consume</span>(<span class="i">SEMICOLON</span>, <span class="s">&quot;Expect &#39;;&#39; after variable declaration.&quot;</span>);
    <span class="k">return</span> <span class="k">new</span> <span class="t">Stmt</span>.<span class="t">Var</span>(<span class="i">name</span>, <span class="i">initializer</span>);
  }
</pre></div>
<div class="source-file-narrow"><em>lox/Parser.java</em>, add after <em>printStatement</em>()</div>

<p>As always, the recursive descent code follows the grammar rule. The parser has
already matched the <code>var</code> token, so next it requires and consumes an identifier
token for the variable name.</p>
<p>Then, if it sees an <code>=</code> token, it knows there is an initializer expression and
parses it. Otherwise, it leaves the initializer <code>null</code>. Finally, it consumes the
required semicolon at the end of the statement. All this gets wrapped in a
Stmt.Var syntax tree node and we&rsquo;re groovy.</p>
<p>Parsing a variable expression is even easier. In <code>primary()</code>, we look for an
identifier token:</p>
<div class="codehilite"><pre class="insert-before">
      return new Expr.Literal(previous().literal);
    }
</pre><div class="source-file"><em>lox/Parser.java</em><br>
in <em>primary</em>()</div>
<pre class="insert">

    <span class="k">if</span> (<span class="i">match</span>(<span class="i">IDENTIFIER</span>)) {
      <span class="k">return</span> <span class="k">new</span> <span class="t">Expr</span>.<span class="t">Variable</span>(<span class="i">previous</span>());
    }
</pre><pre class="insert-after">

    if (match(LEFT_PAREN)) {
</pre></div>
<div class="source-file-narrow"><em>lox/Parser.java</em>, in <em>primary</em>()</div>

<p>That gives us a working front end for declaring and using variables. All that&rsquo;s
left is to feed it into the interpreter. Before we get to that, we need to talk
about where variables live in memory.</p>
<h2><a href="#environments" name="environments"><small>8&#8202;.&#8202;3</small>Environments</a></h2>
<p>The bindings that associate variables to values need to be stored somewhere.
Ever since the Lisp folks invented parentheses, this data structure has been
called an <span name="env"><strong>environment</strong></span>.</p><img src="image/statements-and-state/environment.png" alt="An environment containing two bindings." />
<aside name="env">
<p>I like to imagine the environment literally, as a sylvan wonderland where
variables and values frolic.</p>
</aside>
<p>You can think of it like a <span name="map">map</span> where the keys are
variable names and the values are the variable&rsquo;s, uh, values. In fact, that&rsquo;s
how we&rsquo;ll implement it in Java. We could stuff that map and the code to manage
it right into Interpreter, but since it forms a nicely delineated concept, we&rsquo;ll
pull it out into its own class.</p>
<p>Start a new file and add:</p>
<aside name="map">
<p>Java calls them <strong>maps</strong> or <strong>hashmaps</strong>. Other languages call them <strong>hash
tables</strong>, <strong>dictionaries</strong> (Python and C#), <strong>hashes</strong> (Ruby and Perl),
<strong>tables</strong> (Lua), or <strong>associative arrays</strong> (PHP). Way back when, they were
known as <strong>scatter tables</strong>.</p>
</aside>
<div class="codehilite"><div class="source-file"><em>lox/Environment.java</em><br>
create new file</div>
<pre>
<span class="k">package</span> <span class="i">com.craftinginterpreters.lox</span>;

<span class="k">import</span> <span class="i">java.util.HashMap</span>;
<span class="k">import</span> <span class="i">java.util.Map</span>;

<span class="k">class</span> <span class="t">Environment</span> {
  <span class="k">private</span> <span class="k">final</span> <span class="t">Map</span>&lt;<span class="t">String</span>, <span class="t">Object</span>&gt; <span class="i">values</span> = <span class="k">new</span> <span class="t">HashMap</span>&lt;&gt;();
}
</pre></div>
<div class="source-file-narrow"><em>lox/Environment.java</em>, create new file</div>

<p>There&rsquo;s a Java Map in there to store the bindings. It uses bare strings for the
keys, not tokens. A token represents a unit of code at a specific place in the
source text, but when it comes to looking up variables, all identifier tokens
with the same name should refer to the same variable (ignoring scope for now).
Using the raw string ensures all of those tokens refer to the same map key.</p>
<p>There are two operations we need to support. First, a variable definition binds
a new name to a value.</p>
<div class="codehilite"><div class="source-file"><em>lox/Environment.java</em><br>
in class <em>Environment</em></div>
<pre>
  <span class="t">void</span> <span class="i">define</span>(<span class="t">String</span> <span class="i">name</span>, <span class="t">Object</span> <span class="i">value</span>) {
    <span class="i">values</span>.<span class="i">put</span>(<span class="i">name</span>, <span class="i">value</span>);
  }
</pre></div>
<div class="source-file-narrow"><em>lox/Environment.java</em>, in class <em>Environment</em></div>

<p>Not exactly brain surgery, but we have made one interesting semantic choice.
When we add the key to the map, we don&rsquo;t check to see if it&rsquo;s already present.
That means that this program works:</p>
<div class="codehilite"><pre>
<span class="k">var</span> <span class="i">a</span> = <span class="s">&quot;before&quot;</span>;
<span class="k">print</span> <span class="i">a</span>; <span class="c">// &quot;before&quot;.</span>
<span class="k">var</span> <span class="i">a</span> = <span class="s">&quot;after&quot;</span>;
<span class="k">print</span> <span class="i">a</span>; <span class="c">// &quot;after&quot;.</span>
</pre></div>
<p>A variable statement doesn&rsquo;t just define a <em>new</em> variable, it can also be used
to <em>re</em>-define an existing variable. We could <span name="scheme">choose</span>
to make this an error instead. The user may not intend to redefine an existing
variable. (If they did mean to, they probably would have used assignment, not
<code>var</code>.) Making redefinition an error would help them find that bug.</p>
<p>However, doing so interacts poorly with the REPL. In the middle of a REPL
session, it&rsquo;s nice to not have to mentally track which variables you&rsquo;ve already
defined. We could allow redefinition in the REPL but not in scripts, but then
users have to learn two sets of rules, and code copied and pasted from one form
to the other might not work.</p>
<aside name="scheme">
<p>My rule about variables and scoping is, &ldquo;When in doubt, do what Scheme does.&rdquo;
The Scheme folks have probably spent more time thinking about variable scope
than we ever will<span class="em">&mdash;</span>one of the main goals of Scheme was to introduce lexical
scoping to the world<span class="em">&mdash;</span>so it&rsquo;s hard to go wrong if you follow in their
footsteps.</p>
<p>Scheme allows redefining variables at the top level.</p>
</aside>
<p>So, to keep the two modes consistent, we&rsquo;ll allow it<span class="em">&mdash;</span>at least for global
variables. Once a variable exists, we need a way to look it up.</p>
<div class="codehilite"><pre class="insert-before">

class Environment {
  private final Map&lt;String, Object&gt; values = new HashMap&lt;&gt;();
</pre><div class="source-file"><em>lox/Environment.java</em><br>
in class <em>Environment</em></div>
<pre class="insert">

  <span class="t">Object</span> <span class="i">get</span>(<span class="t">Token</span> <span class="i">name</span>) {
    <span class="k">if</span> (<span class="i">values</span>.<span class="i">containsKey</span>(<span class="i">name</span>.<span class="i">lexeme</span>)) {
      <span class="k">return</span> <span class="i">values</span>.<span class="i">get</span>(<span class="i">name</span>.<span class="i">lexeme</span>);
    }

    <span class="k">throw</span> <span class="k">new</span> <span class="t">RuntimeError</span>(<span class="i">name</span>,
        <span class="s">&quot;Undefined variable &#39;&quot;</span> + <span class="i">name</span>.<span class="i">lexeme</span> + <span class="s">&quot;&#39;.&quot;</span>);
  }

</pre><pre class="insert-after">
  void define(String name, Object value) {
</pre></div>
<div class="source-file-narrow"><em>lox/Environment.java</em>, in class <em>Environment</em></div>

<p>This is a little more semantically interesting. If the variable is found, it
simply returns the value bound to it. But what if it&rsquo;s not? Again, we have a
choice.</p>
<ul>
<li>
<p>Make it a syntax error.</p>
</li>
<li>
<p>Make it a runtime error.</p>
</li>
<li>
<p>Allow it and return some default value like <code>nil</code>.</p>
</li>
</ul>
<p>Lox is pretty lax, but the last option is a little <em>too</em> permissive to me.
Making it a syntax error<span class="em">&mdash;</span>a compile time error<span class="em">&mdash;</span>seems like a smart choice.
Using an undefined variable is a bug, and the sooner you detect the mistake, the
better.</p>
<p>The problem is that <em>using</em> a variable isn&rsquo;t the same as <em>referring to it</em>. You
can refer to a variable in a chunk of code without immediately evaluating it if
that chunk of code is wrapped inside a function. If we make it a static error to
<em>mention</em> a variable before it&rsquo;s been declared, it becomes much harder to define
recursive functions.</p>
<p>We could accommodate single recursion<span class="em">&mdash;</span>a function that calls itself<span class="em">&mdash;</span>by
declaring the function&rsquo;s own name before we examine its body. But that doesn&rsquo;t
help with mutually recursive procedures that call each other. Consider:</p>
<p><span name="contrived"></span></p>
<div class="codehilite"><pre>
<span class="k">fun</span> <span class="i">isOdd</span>(<span class="i">n</span>) {
  <span class="k">if</span> (<span class="i">n</span> == <span class="n">0</span>) <span class="k">return</span> <span class="k">false</span>;
  <span class="k">return</span> <span class="i">isEven</span>(<span class="i">n</span> - <span class="n">1</span>);
}

<span class="k">fun</span> <span class="i">isEven</span>(<span class="i">n</span>) {
  <span class="k">if</span> (<span class="i">n</span> == <span class="n">0</span>) <span class="k">return</span> <span class="k">true</span>;
  <span class="k">return</span> <span class="i">isOdd</span>(<span class="i">n</span> - <span class="n">1</span>);
}
</pre></div>
<aside name="contrived">
<p>Granted, this is probably not the most efficient way to tell if a number is even
or odd (not to mention the bad things that happen if you pass a non-integer or
negative number to them). Bear with me.</p>
</aside>
<p>The <code>isEven()</code> function isn&rsquo;t defined by the <span name="declare">time</span> we
are looking at the body of <code>isOdd()</code> where it&rsquo;s called. If we swap the order of
the two functions, then <code>isOdd()</code> isn&rsquo;t defined when we&rsquo;re looking at
<code>isEven()</code>&rsquo;s body.</p>
<aside name="declare">
<p>Some statically-typed languages like Java and C# solve this by specifying that
the top level of a program isn&rsquo;t a sequence of imperative statements. Instead, a
program is a set of declarations which all come into being simultaneously. The
implementation declares <em>all</em> of the names before looking at the bodies of <em>any</em>
of the functions.</p>
<p>Older languages like C and Pascal don&rsquo;t work like this. Instead, they force you
to add explicit <em>forward declarations</em> to declare a name before it&rsquo;s fully
defined. That was a concession to the limited computing power at the time. They
wanted to be able to compile a source file in one single pass through the text,
so those compilers couldn&rsquo;t gather up all of the declarations first before
processing function bodies.</p>
</aside>
<p>Since making it a <em>static</em> error makes recursive declarations too difficult,
we&rsquo;ll defer the error to runtime. It&rsquo;s OK to refer to a variable before it&rsquo;s
defined as long as you don&rsquo;t <em>evaluate</em> the reference. That lets the program
for even and odd numbers work, but you&rsquo;d get a runtime error in:</p>
<div class="codehilite"><pre>
<span class="k">print</span> <span class="i">a</span>;
<span class="k">var</span> <span class="i">a</span> = <span class="s">&quot;too late!&quot;</span>;
</pre></div>
<p>As with type errors in the expression evaluation code, we report a runtime error
by throwing an exception. The exception contains the variable&rsquo;s token so we can
tell the user where in their code they messed up.</p>
<h3><a href="#interpreting-global-variables" name="interpreting-global-variables"><small>8&#8202;.&#8202;3&#8202;.&#8202;1</small>Interpreting global variables</a></h3>
<p>The Interpreter class gets an instance of the new Environment class.</p>
<div class="codehilite"><pre class="insert-before">
                             Stmt.Visitor&lt;Void&gt; {
</pre><div class="source-file"><em>lox/Interpreter.java</em><br>
in class <em>Interpreter</em></div>
<pre class="insert">
  <span class="k">private</span> <span class="t">Environment</span> <span class="i">environment</span> = <span class="k">new</span> <span class="t">Environment</span>();

</pre><pre class="insert-after">
  void interpret(List&lt;Stmt&gt; statements) {
</pre></div>
<div class="source-file-narrow"><em>lox/Interpreter.java</em>, in class <em>Interpreter</em></div>

<p>We store it as a field directly in Interpreter so that the variables stay in
memory as long as the interpreter is still running.</p>
<p>We have two new syntax trees, so that&rsquo;s two new visit methods. The first is for
declaration statements.</p>
<div class="codehilite"><div class="source-file"><em>lox/Interpreter.java</em><br>
add after <em>visitPrintStmt</em>()</div>
<pre>
  <span class="a">@Override</span>
  <span class="k">public</span> <span class="t">Void</span> <span class="i">visitVarStmt</span>(<span class="t">Stmt</span>.<span class="t">Var</span> <span class="i">stmt</span>) {
    <span class="t">Object</span> <span class="i">value</span> = <span class="k">null</span>;
    <span class="k">if</span> (<span class="i">stmt</span>.<span class="i">initializer</span> != <span class="k">null</span>) {
      <span class="i">value</span> = <span class="i">evaluate</span>(<span class="i">stmt</span>.<span class="i">initializer</span>);
    }

    <span class="i">environment</span>.<span class="i">define</span>(<span class="i">stmt</span>.<span class="i">name</span>.<span class="i">lexeme</span>, <span class="i">value</span>);
    <span class="k">return</span> <span class="k">null</span>;
  }
</pre></div>
<div class="source-file-narrow"><em>lox/Interpreter.java</em>, add after <em>visitPrintStmt</em>()</div>

<p>If the variable has an initializer, we evaluate it. If not, we have another
choice to make. We could have made this a syntax error in the parser by
<em>requiring</em> an initializer. Most languages don&rsquo;t, though, so it feels a little
harsh to do so in Lox.</p>
<p>We could make it a runtime error. We&rsquo;d let you define an uninitialized variable,
but if you accessed before assigning to it, a runtime error would occur. It&rsquo;s
not a bad idea, but most dynamically typed languages don&rsquo;t do that. Instead,
we&rsquo;ll keep it simple and say that Lox sets a variable to <code>nil</code> if it isn&rsquo;t
explicitly initialized.</p>
<div class="codehilite"><pre>
<span class="k">var</span> <span class="i">a</span>;
<span class="k">print</span> <span class="i">a</span>; <span class="c">// &quot;nil&quot;.</span>
</pre></div>
<p>Thus, if there isn&rsquo;t an initializer, we set the value to <code>null</code>, which is the
Java representation of Lox&rsquo;s <code>nil</code> value. Then we tell the environment to bind
the variable to that value.</p>
<p>Next, to evaluate a variable expression.</p>
<div class="codehilite"><div class="source-file"><em>lox/Interpreter.java</em><br>
add after <em>visitUnaryExpr</em>()</div>
<pre>
  <span class="a">@Override</span>
  <span class="k">public</span> <span class="t">Object</span> <span class="i">visitVariableExpr</span>(<span class="t">Expr</span>.<span class="t">Variable</span> <span class="i">expr</span>) {
    <span class="k">return</span> <span class="i">environment</span>.<span class="i">get</span>(<span class="i">expr</span>.<span class="i">name</span>);
  }
</pre></div>
<div class="source-file-narrow"><em>lox/Interpreter.java</em>, add after <em>visitUnaryExpr</em>()</div>

<p>This simply forwards to the environment which does the heavy lifting to make
sure the variable is defined. With that, we&rsquo;ve got rudimentary variables
working. Try this out:</p>
<div class="codehilite"><pre>
<span class="k">var</span> <span class="i">a</span> = <span class="n">1</span>;
<span class="k">var</span> <span class="i">b</span> = <span class="n">2</span>;
<span class="k">print</span> <span class="i">a</span> + <span class="i">b</span>;
</pre></div>
<p>We can&rsquo;t reuse <em>code</em> yet, but we can start to build up programs that reuse
<em>data</em>.</p>
<h2><a href="#assignment" name="assignment"><small>8&#8202;.&#8202;4</small>Assignment</a></h2>
<p>It&rsquo;s possible to create a language that has variables but does not let you
reassign<span class="em">&mdash;</span>or <strong>mutate</strong><span class="em">&mdash;</span>them. Haskell is one example. SML only supports
mutable references and arrays<span class="em">&mdash;</span>variables cannot be re-assigned. Rust steers
you away from mutation by requiring a <code>mut</code> modifier to enable assignment.</p>
<p>Mutating a variable is a side effect and, as the name suggests, some language
folks think side effects are <span name="pure">dirty</span> or inelegant. Code
should be pure math that produces values<span class="em">&mdash;</span>crystalline, unchanging ones<span class="em">&mdash;</span>like
an act of divine creation. Not some grubby automaton that beats blobs of data
into shape, one imperative grunt at a time.</p>
<aside name="pure">
<p>I find it delightful that the same group of people who pride themselves on
dispassionate logic are also the ones who can&rsquo;t resist emotionally-loaded terms
for their work: &ldquo;pure&rdquo;, &ldquo;side effect&rdquo;, &ldquo;lazy&rdquo;, &ldquo;persistent&rdquo;, &ldquo;first-class&rdquo;,
&ldquo;higher-order&rdquo;.</p>
</aside>
<p>Lox is not so austere. Lox is an imperative language, and mutation comes with
the territory. Adding support for assignment doesn&rsquo;t require much work. Global
variables already support redefinition, so most of the machinery is there now.
Mainly, we&rsquo;re missing an explicit assignment notation.</p>
<h3><a href="#assignment-syntax" name="assignment-syntax"><small>8&#8202;.&#8202;4&#8202;.&#8202;1</small>Assignment syntax</a></h3>
<p>That little <code>=</code> syntax is more complex than it might seem. Like most C-derived
languages, assignment is an <span name="assign">expression</span> and not a
statement. As in C, it is the lowest precedence expression form. That means the
rule slots between <code>expression</code> and <code>equality</code>, the next lowest precedence
expression.</p>
<aside name="assign">
<p>In some other languages, like Pascal, Python, and Go, assignment is a statement.</p>
</aside>
<div class="codehilite"><pre>
<span class="i">expression</span>     → <span class="i">assignment</span> ;
<span class="i">assignment</span>     → <span class="t">IDENTIFIER</span> <span class="s">&quot;=&quot;</span> <span class="i">assignment</span>
               | <span class="i">equality</span> ;
</pre></div>
<p>This says an <code>assignment</code> is either an identifier followed by an <code>=</code> and an
expression for the value, or an <code>equality</code> (and thus any other) expression.
Later, <code>assignment</code> will get more complex when we add property setters on
objects, like:</p>
<div class="codehilite"><pre>
<span class="i">instance</span>.<span class="i">field</span> = <span class="s">&quot;value&quot;</span>;
</pre></div>
<p>The easy part is adding the <span name="assign-ast">new syntax tree node</span>.</p>
<div class="codehilite"><pre class="insert-before">
    defineAst(outputDir, &quot;Expr&quot;, Arrays.asList(
</pre><div class="source-file"><em>tool/GenerateAst.java</em><br>
in <em>main</em>()</div>
<pre class="insert">
      <span class="s">&quot;Assign   : Token name, Expr value&quot;</span>,
</pre><pre class="insert-after">
      &quot;Binary   : Expr left, Token operator, Expr right&quot;,
</pre></div>
<div class="source-file-narrow"><em>tool/GenerateAst.java</em>, in <em>main</em>()</div>

<aside name="assign-ast">
<p>The generated code for the new node is in <a href="appendix-ii.html#assign-expression">Appendix II</a>.</p>
</aside>
<p>It has a token for the variable being assigned to, and an expression for the new
value. After you run the AstGenerator to get the new Expr.Assign class, swap out
the body of the parser&rsquo;s existing <code>expression()</code> method to match the updated
rule.</p>
<div class="codehilite"><pre class="insert-before">
  private Expr expression() {
</pre><div class="source-file"><em>lox/Parser.java</em><br>
in <em>expression</em>()<br>
replace 1 line</div>
<pre class="insert">
    <span class="k">return</span> <span class="i">assignment</span>();
</pre><pre class="insert-after">
  }
</pre></div>
<div class="source-file-narrow"><em>lox/Parser.java</em>, in <em>expression</em>(), replace 1 line</div>

<p>Here is where it gets tricky. A single token lookahead recursive descent parser
can&rsquo;t see far enough to tell that it&rsquo;s parsing an assignment until <em>after</em> it
has gone through the left-hand side and stumbled onto the <code>=</code>. You might wonder
why it even needs to. After all, we don&rsquo;t know we&rsquo;re parsing a <code>+</code> expression
until after we&rsquo;ve finished parsing the left operand.</p>
<p>The difference is that the left-hand side of an assignment isn&rsquo;t an expression
that evaluates to a value. It&rsquo;s a sort of pseudo-expression that evaluates to a
&ldquo;thing&rdquo; you can assign to. In:</p>
<div class="codehilite"><pre>
<span class="k">var</span> <span class="i">a</span> = <span class="s">&quot;before&quot;</span>;
<span class="i">a</span> = <span class="s">&quot;value&quot;</span>;
</pre></div>
<p>On the second line, we don&rsquo;t <em>evaluate</em> <code>a</code> (which would return the string
&ldquo;before&rdquo;). We figure out what variable <code>a</code> refers to so we know where to store
the right-hand side expression&rsquo;s value. The <a href="https://en.wikipedia.org/wiki/Value_(computer_science)#lrvalue">classic terms</a> for these
two <span name="l-value">constructs</span> are <strong>l-value</strong> and <strong>r-value</strong>. All
of the expressions that we&rsquo;ve seen so far that produce values are r-values. An
l-value &ldquo;evaluates&rdquo; to a storage location that you can assign into.</p>
<aside name="l-value">
<p>In fact, the names come from assignment expressions: <em>l</em>-values appear on the
<em>left</em> side of the <code>=</code> in an assignment, and <em>r</em>-values on the <em>right</em>.</p>
</aside>
<p>We want the syntax tree to reflect that an l-value isn&rsquo;t evaluated like a normal
expression. That&rsquo;s why the Expr.Assign node has a <em>Token</em> for the left-hand
side, not an Expr. The problem is that the parser doesn&rsquo;t know it&rsquo;s parsing an
l-value until it hits the <code>=</code>. In a complex l-value, that may occur <span
name="many">many</span> tokens later:</p>
<div class="codehilite"><pre>
<span class="i">makeList</span>().<span class="i">head</span>.<span class="i">next</span> = <span class="i">node</span>;
</pre></div>
<aside name="many">
<p>Since the receiver of a field assignment can be any expression, and expressions
can be as long as you want to make them, it may take an <em>unbounded</em> number of
tokens of lookahead to find the <code>=</code>.</p>
</aside>
<p>We only have a single token of lookahead, so what do we do? We use a little
trick, and it looks like this:</p>
<div class="codehilite"><div class="source-file"><em>lox/Parser.java</em><br>
add after <em>expressionStatement</em>()</div>
<pre>
  <span class="k">private</span> <span class="t">Expr</span> <span class="i">assignment</span>() {
    <span class="t">Expr</span> <span class="i">expr</span> = <span class="i">equality</span>();

    <span class="k">if</span> (<span class="i">match</span>(<span class="i">EQUAL</span>)) {
      <span class="t">Token</span> <span class="i">equals</span> = <span class="i">previous</span>();
      <span class="t">Expr</span> <span class="i">value</span> = <span class="i">assignment</span>();

      <span class="k">if</span> (<span class="i">expr</span> <span class="k">instanceof</span> <span class="t">Expr</span>.<span class="t">Variable</span>) {
        <span class="t">Token</span> <span class="i">name</span> = ((<span class="t">Expr</span>.<span class="t">Variable</span>)<span class="i">expr</span>).<span class="i">name</span>;
        <span class="k">return</span> <span class="k">new</span> <span class="t">Expr</span>.<span class="t">Assign</span>(<span class="i">name</span>, <span class="i">value</span>);
      }

      <span class="i">error</span>(<span class="i">equals</span>, <span class="s">&quot;Invalid assignment target.&quot;</span>);<span name="no-throw"> </span>
    }

    <span class="k">return</span> <span class="i">expr</span>;
  }
</pre></div>
<div class="source-file-narrow"><em>lox/Parser.java</em>, add after <em>expressionStatement</em>()</div>

<p>Most of the code for parsing an assignment expression looks similar to the other
binary operators like <code>+</code>. We parse the left-hand side, which can be any
expression of higher precedence. If we find an <code>=</code>, we parse the right-hand side
and then wrap it all up in an assignment expression tree node.</p>
<aside name="no-throw">
<p>We <em>report</em> an error if the left-hand side isn&rsquo;t a valid assignment target, but
we don&rsquo;t <em>throw</em> it because the parser isn&rsquo;t in a confused state where we need
to go into panic mode and synchronize.</p>
</aside>
<p>One slight difference from binary operators is that we don&rsquo;t loop to build up a
sequence of the same operator. Since assignment is right-associative, we instead
recursively call <code>assignment()</code> to parse the right-hand side.</p>
<p>The trick is that right before we create the assignment expression node, we look
at the left-hand side expression and figure out what kind of assignment target
it is. We convert the r-value expression node into an l-value representation.</p>
<p>This trick works because it turns out that every valid assignment target happens
to also be <span name="converse">valid syntax</span> as a normal expression.
Consider a complex field assignment like:</p>
<aside name="converse">
<p>You can still use this trick even if there are assignment targets that are not
valid expressions. Define a <strong>cover grammar</strong>, a looser grammar that accepts
both all of the valid expression <em>and</em> assignment target syntaxes. When you hit
an <code>=</code>, report an error if the left-hand side isn&rsquo;t within the valid assignment
target grammar. Conversely, if you <em>don&rsquo;t</em> hit an <code>=</code>, report an error if the
left-hand side isn&rsquo;t a valid <em>expression</em>.</p>
</aside>
<div class="codehilite"><pre>
<span class="i">newPoint</span>(<span class="i">x</span> + <span class="n">2</span>, <span class="n">0</span>).<span class="i">y</span> = <span class="n">3</span>;
</pre></div>
<p>The left-hand side of that assignment could also work as a valid expression:</p>
<div class="codehilite"><pre>
<span class="i">newPoint</span>(<span class="i">x</span> + <span class="n">2</span>, <span class="n">0</span>).<span class="i">y</span>;
</pre></div>
<p>(Where the first example sets the field, the second gets it.)</p>
<p>This means we can parse the left-hand side as <em>if it were</em> an expression and
then after the fact produce a syntax tree that turns it into an assignment
target. If the left-hand side expression isn&rsquo;t a <span name="paren">valid</span>
assignment target, we fail with a syntax error. That ensures we report an error
on code like:</p>
<div class="codehilite"><pre>
<span class="i">a</span> + <span class="i">b</span> = <span class="i">c</span>;
</pre></div>
<aside name="paren">
<p>Do you remember way back in the parsing chapter when I said we represent
parenthesized expressions in the syntax tree because we&rsquo;ll need them later? This
is why. We need to keep track of them so that we can distinguish between:</p>
<div class="codehilite"><pre>
<span class="i">a</span> = <span class="n">3</span>;   <span class="c">// OK.</span>
(<span class="i">a</span>) = <span class="n">3</span>; <span class="c">// Error.</span>
</pre></div>
</aside>
<p>Right now, the only valid target is a simple variable expression, but we&rsquo;ll add
fields later. The end result of this trick is an assignment expression tree node
that knows what it is assigning to and has an expression subtree for the value
being assigned. All with only a single token of lookahead and no backtracking.</p>
<h3><a href="#assignment-semantics" name="assignment-semantics"><small>8&#8202;.&#8202;4&#8202;.&#8202;2</small>Assignment semantics</a></h3>
<p>We have a new syntax tree node, so our interpreter gets a new visit method.</p>
<div class="codehilite"><div class="source-file"><em>lox/Interpreter.java</em><br>
add after <em>visitVarStmt</em>()</div>
<pre>
  <span class="a">@Override</span>
  <span class="k">public</span> <span class="t">Object</span> <span class="i">visitAssignExpr</span>(<span class="t">Expr</span>.<span class="t">Assign</span> <span class="i">expr</span>) {
    <span class="t">Object</span> <span class="i">value</span> = <span class="i">evaluate</span>(<span class="i">expr</span>.<span class="i">value</span>);
    <span class="i">environment</span>.<span class="i">assign</span>(<span class="i">expr</span>.<span class="i">name</span>, <span class="i">value</span>);
    <span class="k">return</span> <span class="i">value</span>;
  }
</pre></div>
<div class="source-file-narrow"><em>lox/Interpreter.java</em>, add after <em>visitVarStmt</em>()</div>

<p>For obvious reasons, it&rsquo;s similar to variable declaration. It evaluates the
right-hand side to get the value, then stores it in the named variable. Instead
of using <code>define()</code> on Environment, it calls this new method:</p>
<div class="codehilite"><div class="source-file"><em>lox/Environment.java</em><br>
add after <em>get</em>()</div>
<pre>
  <span class="t">void</span> <span class="i">assign</span>(<span class="t">Token</span> <span class="i">name</span>, <span class="t">Object</span> <span class="i">value</span>) {
    <span class="k">if</span> (<span class="i">values</span>.<span class="i">containsKey</span>(<span class="i">name</span>.<span class="i">lexeme</span>)) {
      <span class="i">values</span>.<span class="i">put</span>(<span class="i">name</span>.<span class="i">lexeme</span>, <span class="i">value</span>);
      <span class="k">return</span>;
    }

    <span class="k">throw</span> <span class="k">new</span> <span class="t">RuntimeError</span>(<span class="i">name</span>,
        <span class="s">&quot;Undefined variable &#39;&quot;</span> + <span class="i">name</span>.<span class="i">lexeme</span> + <span class="s">&quot;&#39;.&quot;</span>);
  }
</pre></div>
<div class="source-file-narrow"><em>lox/Environment.java</em>, add after <em>get</em>()</div>

<p>The key difference between assignment and definition is that assignment is not
<span name="new">allowed</span> to create a <em>new</em> variable. In terms of our
implementation, that means it&rsquo;s a runtime error if the key doesn&rsquo;t already exist
in the environment&rsquo;s variable map.</p>
<aside name="new">
<p>Unlike Python and Ruby, Lox doesn&rsquo;t do <a href="#design-note">implicit variable declaration</a>.</p>
</aside>
<p>The last thing the <code>visit()</code> method does is return the assigned value. That&rsquo;s
because assignment is an expression that can be nested inside other expressions,
like so:</p>
<div class="codehilite"><pre>
<span class="k">var</span> <span class="i">a</span> = <span class="n">1</span>;
<span class="k">print</span> <span class="i">a</span> = <span class="n">2</span>; <span class="c">// &quot;2&quot;.</span>
</pre></div>
<p>Our interpreter can now create, read, and modify variables. It&rsquo;s about as
sophisticated as early <span name="basic">BASICs</span>. Global variables are
simple, but writing a large program when any two chunks of code can accidentally
step on each other&rsquo;s state is no fun. We want <em>local</em> variables, which means
it&rsquo;s time for <em>scope</em>.</p>
<aside name="basic">
<p>Maybe a little better than that. Unlike some old BASICs, Lox can handle variable
names longer than two characters</p>
</aside>
<h2><a href="#scope" name="scope"><small>8&#8202;.&#8202;5</small>Scope</a></h2>
<p>A <strong>scope</strong> defines a region where a name maps to a certain entity. Multiple
scopes enable the same name to refer to different things in different contexts.
In my house, &ldquo;Bob&rdquo; usually refers to me. But maybe in your town you know a
different Bob. Same name, but different dudes based on where you say it.</p>
<p><span name="lexical"><strong>Lexical scope</strong></span> (or the less commonly heard
<strong>static scope</strong>) is a specific style of scoping where the text of the program
itself shows where a scope begins and ends. In Lox, as in most modern languages,
variables are lexically scoped. When you see an expression that uses some
variable, you can figure out which variable declaration it refers to just by
statically reading the code.</p>
<aside name="lexical">
<p>&ldquo;Lexical&rdquo; comes from the Greek &ldquo;lexikos&rdquo; which means &ldquo;related to words&rdquo;. When we
use it in programming languages, it usually means a thing you can figure out
from source code itself without having to execute anything.</p>
<p>Lexical scope came onto the scene with ALGOL. Earlier languages were often
dynamically scoped. Computer scientists back then believed dynamic scope was
faster to execute. Today, thanks to early Scheme hackers, we know that isn&rsquo;t
true. If anything, it&rsquo;s the opposite.</p>
<p>Dynamic scope for variables lives on in some corners. Emacs Lisp defaults to
dynamic scope for variables. The <a href="http://clojuredocs.org/clojure.core/binding"><code>binding</code></a> macro in Clojure provides
it. The widely-disliked <a href="https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Statements/with"><code>with</code> statement</a> in JavaScript turns properties
on an object into dynamically-scoped variables.</p>
</aside>
<p>For example:</p>
<div class="codehilite"><pre>
{
  <span class="k">var</span> <span class="i">a</span> = <span class="s">&quot;first&quot;</span>;
  <span class="k">print</span> <span class="i">a</span>; <span class="c">// &quot;first&quot;.</span>
}

{
  <span class="k">var</span> <span class="i">a</span> = <span class="s">&quot;second&quot;</span>;
  <span class="k">print</span> <span class="i">a</span>; <span class="c">// &quot;second&quot;.</span>
}
</pre></div>
<p>Here, we have two blocks and a variable <code>a</code> is declared in each of them. You and
I can tell just from looking at the code that the use of <code>a</code> in the first
<code>print</code> statement refers to the first <code>a</code>, and the second one refers to the
second.</p><img src="image/statements-and-state/blocks.png" alt="An environment for each 'a'." />
<p>This is in contrast with <strong>dynamic scope</strong> where you don&rsquo;t know what a name
refers to until you execute the code. Lox doesn&rsquo;t have dynamically scoped
<em>variables</em>, but methods and fields on objects are dynamically scoped.</p>
<div class="codehilite"><pre>
<span class="k">class</span> <span class="t">Saxophone</span> {
  <span class="i">play</span>() {
    <span class="k">print</span> <span class="s">&quot;Careless Whisper&quot;</span>;
  }
}

<span class="k">class</span> <span class="t">GolfClub</span> {
  <span class="i">play</span>() {
    <span class="k">print</span> <span class="s">&quot;Fore!&quot;</span>;
  }
}

<span class="k">fun</span> <span class="i">playIt</span>(<span class="i">thing</span>) {
  <span class="i">thing</span>.<span class="i">play</span>();
}
</pre></div>
<p>When <code>playIt()</code> calls <code>thing.play()</code>, we don&rsquo;t know if we&rsquo;re about to hear
&ldquo;Careless Whisper&rdquo; or &ldquo;Fore!&rdquo;. It depends on whether you pass a Saxophone or a
GolfClub to the function, and we don&rsquo;t know that until runtime.</p>
<p>Scope and environments are close cousins. The former is the theoretical concept,
and the latter machinery implements it. As our interpreter works its way through
code, syntax tree nodes that affect scope will change the environment. In a
C-ish syntax like Lox&rsquo;s, scope is controlled by curly-braced <span
name="block">blocks</span>. (That&rsquo;s why we call it <strong>block scope</strong>.)</p>
<div class="codehilite"><pre>
{
  <span class="k">var</span> <span class="i">a</span> = <span class="s">&quot;in block&quot;</span>;
}
<span class="k">print</span> <span class="i">a</span>; <span class="c">// Error! No more &quot;a&quot;.</span>
</pre></div>
<p>The beginning of a block introduces a new local scope, and that scope ends when
execution passes the closing <code>}</code>. Any variables declared inside the block
disappear.</p>
<h3><a href="#nesting-and-shadowing" name="nesting-and-shadowing"><small>8&#8202;.&#8202;5&#8202;.&#8202;1</small>Nesting and shadowing</a></h3>
<p>A first cut at implementing block scope might work like this:</p>
<ol>
<li>
<p>As we visit each statement inside the block, keep track of any variables
declared.</p>
</li>
<li>
<p>After the last statement is executed, tell the environment to delete all of
those variables.</p>
</li>
</ol>
<p>That would work for the previous example. But, remember, one motivation for
local scope is encapsulation<span class="em">&mdash;</span>a block of code in one corner of the program
shouldn&rsquo;t interfere with some other one. Check this out:</p>
<div class="codehilite"><pre>
<span class="c">// How loud?</span>
<span class="k">var</span> <span class="i">volume</span> = <span class="n">11</span>;

<span class="c">// Silence.</span>
<span class="i">volume</span> = <span class="n">0</span>;

<span class="c">// Calculate size of 3x4x5 cuboid.</span>
{
  <span class="k">var</span> <span class="i">volume</span> = <span class="n">3</span> * <span class="n">4</span> * <span class="n">5</span>;
  <span class="k">print</span> <span class="i">volume</span>;
}
</pre></div>
<p>Look at the block where we calculate the volume of the cuboid using a local
declaration of <code>volume</code>. After the block exits, the interpreter will delete the
<em>global</em> <code>volume</code> variable. That ain&rsquo;t right. When we exit the block, we should
remove any variables declared inside the block, but if there is a variable with
the same name declared outside of the block, <em>that&rsquo;s a different variable</em>. It
doesn&rsquo;t get touched.</p>
<p>When a local variable has the same name as a variable in an enclosing scope, it
<strong>shadows</strong> the outer one. Code inside the block can&rsquo;t see it any more<span class="em">&mdash;</span>it is
hidden in the &ldquo;shadow&rdquo; cast by the inner one<span class="em">&mdash;</span>but it&rsquo;s still there.</p>
<p>When we enter a new block scope, we need to preserve variables defined in outer
scopes so they are still around when we exit the inner block. We do that by
defining a fresh environment for each block containing only the variables
defined in that scope. When we exit the block, we discard its environment and
restore the previous one.</p>
<p>We also need to handle enclosing variables that are <em>not</em> shadowed.</p>
<div class="codehilite"><pre>
<span class="k">var</span> <span class="i">global</span> = <span class="s">&quot;outside&quot;</span>;
{
  <span class="k">var</span> <span class="i">local</span> = <span class="s">&quot;inside&quot;</span>;
  <span class="k">print</span> <span class="i">global</span> + <span class="i">local</span>;
}
</pre></div>
<p>Here, <code>global</code> lives in the outer global environment and <code>local</code> is defined
inside the block&rsquo;s environment. In that <code>print</code> statement, both of those
variables are in scope. In order to find them, the interpreter must search not
only the current innermost environment, but also any enclosing ones.</p>
<p>We implement this by <span name="cactus">chaining</span> the environments
together. Each environment has a reference to the environment of the immediately
enclosing scope. When we look up a variable, we walk that chain from innermost
out until we find the variable. Starting at the inner scope is how we make local
variables shadow outer ones.</p><img src="image/statements-and-state/chaining.png" alt="Environments for each scope, linked together." />
<aside name="cactus">
<p>While the interpreter is running, the environments form a linear list of
objects, but consider the full set of environments created during the entire
execution. An outer scope may have multiple blocks nested within it, and each
will point to the outer one, giving a tree-like structure, though only one path
through the tree exists at a time.</p>
<p>The boring name for this is a <a href="https://en.wikipedia.org/wiki/Parent_pointer_tree"><strong>parent-pointer tree</strong></a>, but I
much prefer the evocative <strong>cactus stack</strong>.</p><img class="above" src="image/statements-and-state/cactus.png" alt="Each branch points to its parent. The root is global scope.">
</aside>
<p>Before we add block syntax to the grammar, we&rsquo;ll beef up our Environment class
with support for this nesting. First, we give each environment a reference to
its enclosing one.</p>
<div class="codehilite"><pre class="insert-before">
class Environment {
</pre><div class="source-file"><em>lox/Environment.java</em><br>
in class <em>Environment</em></div>
<pre class="insert">
  <span class="k">final</span> <span class="t">Environment</span> <span class="i">enclosing</span>;
</pre><pre class="insert-after">
  private final Map&lt;String, Object&gt; values = new HashMap&lt;&gt;();
</pre></div>
<div class="source-file-narrow"><em>lox/Environment.java</em>, in class <em>Environment</em></div>

<p>This field needs to be initialized, so we add a couple of constructors:</p>
<div class="codehilite"><div class="source-file"><em>lox/Environment.java</em><br>
in class <em>Environment</em></div>
<pre>
  <span class="t">Environment</span>() {
    <span class="i">enclosing</span> = <span class="k">null</span>;
  }

  <span class="t">Environment</span>(<span class="t">Environment</span> <span class="i">enclosing</span>) {
    <span class="k">this</span>.<span class="i">enclosing</span> = <span class="i">enclosing</span>;
  }
</pre></div>
<div class="source-file-narrow"><em>lox/Environment.java</em>, in class <em>Environment</em></div>

<p>The no-argument constructor is for the global scope&rsquo;s environment, which ends
the chain. The other constructor creates a new local scope nested inside the
given outer one.</p>
<p>We don&rsquo;t have to touch the <code>define()</code> method<span class="em">&mdash;</span>a new variable is always
declared in the current innermost scope. But variable lookup and assignment work
with existing variables and they need to walk the chain to find them. First,
lookup.</p>
<div class="codehilite"><pre class="insert-before">
      return values.get(name.lexeme);
    }
</pre><div class="source-file"><em>lox/Environment.java</em><br>
in <em>get</em>()</div>
<pre class="insert">

    <span class="k">if</span> (<span class="i">enclosing</span> != <span class="k">null</span>) <span class="k">return</span> <span class="i">enclosing</span>.<span class="i">get</span>(<span class="i">name</span>);
</pre><pre class="insert-after">

    throw new RuntimeError(name,
        &quot;Undefined variable '&quot; + name.lexeme + &quot;'.&quot;);
</pre></div>
<div class="source-file-narrow"><em>lox/Environment.java</em>, in <em>get</em>()</div>

<p>If the variable isn&rsquo;t found in this environment, we simply try the enclosing
one. That in turn does the same thing <span name="recurse">recursively</span>,
so this will ultimately walk the entire chain. If we reach an environment with
no enclosing one and still don&rsquo;t find the variable, then we give up and report
an error as before.</p>
<p>Assignment works the same way.</p>
<aside name="recurse">
<p>It&rsquo;s likely faster to iteratively walk the chain, but I think the recursive
solution is prettier. We&rsquo;ll do something <em>much</em> faster in clox.</p>
</aside>
<div class="codehilite"><pre class="insert-before">
      values.put(name.lexeme, value);
      return;
    }

</pre><div class="source-file"><em>lox/Environment.java</em><br>
in <em>assign</em>()</div>
<pre class="insert">
    <span class="k">if</span> (<span class="i">enclosing</span> != <span class="k">null</span>) {
      <span class="i">enclosing</span>.<span class="i">assign</span>(<span class="i">name</span>, <span class="i">value</span>);
      <span class="k">return</span>;
    }

</pre><pre class="insert-after">
    throw new RuntimeError(name,
</pre></div>
<div class="source-file-narrow"><em>lox/Environment.java</em>, in <em>assign</em>()</div>

<p>Again, if the variable isn&rsquo;t in this environment, it checks the outer one,
recursively.</p>
<h3><a href="#block-syntax-and-semantics" name="block-syntax-and-semantics"><small>8&#8202;.&#8202;5&#8202;.&#8202;2</small>Block syntax and semantics</a></h3>
<p>Now that Environments nest, we&rsquo;re ready to add blocks to the language. Behold
the grammar:</p>
<div class="codehilite"><pre>
<span class="i">statement</span>      → <span class="i">exprStmt</span>
               | <span class="i">printStmt</span>
               | <span class="i">block</span> ;

<span class="i">block</span>          → <span class="s">&quot;{&quot;</span> <span class="i">declaration</span>* <span class="s">&quot;}&quot;</span> ;
</pre></div>
<p>A block is a (possibly empty) series of statements or declarations surrounded by
curly braces. A block is itself a statement and can appear anywhere a statement
is allowed. The <span name="block-ast">syntax tree</span> node looks like this:</p>
<div class="codehilite"><pre class="insert-before">
    defineAst(outputDir, &quot;Stmt&quot;, Arrays.asList(
</pre><div class="source-file"><em>tool/GenerateAst.java</em><br>
in <em>main</em>()</div>
<pre class="insert">
      <span class="s">&quot;Block      : List&lt;Stmt&gt; statements&quot;</span>,
</pre><pre class="insert-after">
      &quot;Expression : Expr expression&quot;,
</pre></div>
<div class="source-file-narrow"><em>tool/GenerateAst.java</em>, in <em>main</em>()</div>

<aside name="block-ast">
<p>The generated code for the new node is in <a href="appendix-ii.html#block-statement">Appendix II</a>.</p>
</aside>
<p><span name="generate">It</span> contains the list of statements that are inside
the block. Parsing is straightforward. Like other statements, we detect the
beginning of a block by its leading token<span class="em">&mdash;</span>in this case the <code>{</code>. In the
<code>statement()</code> method, we add:</p>
<aside name="generate">
<p>As always, don&rsquo;t forget to run &ldquo;GenerateAst.java&rdquo;.</p>
</aside>
<div class="codehilite"><pre class="insert-before">
    if (match(PRINT)) return printStatement();
</pre><div class="source-file"><em>lox/Parser.java</em><br>
in <em>statement</em>()</div>
<pre class="insert">
    <span class="k">if</span> (<span class="i">match</span>(<span class="i">LEFT_BRACE</span>)) <span class="k">return</span> <span class="k">new</span> <span class="t">Stmt</span>.<span class="t">Block</span>(<span class="i">block</span>());
</pre><pre class="insert-after">

    return expressionStatement();
</pre></div>
<div class="source-file-narrow"><em>lox/Parser.java</em>, in <em>statement</em>()</div>

<p>All the real work happens here:</p>
<div class="codehilite"><div class="source-file"><em>lox/Parser.java</em><br>
add after <em>expressionStatement</em>()</div>
<pre>
  <span class="k">private</span> <span class="t">List</span>&lt;<span class="t">Stmt</span>&gt; <span class="i">block</span>() {
    <span class="t">List</span>&lt;<span class="t">Stmt</span>&gt; <span class="i">statements</span> = <span class="k">new</span> <span class="t">ArrayList</span>&lt;&gt;();

    <span class="k">while</span> (!<span class="i">check</span>(<span class="i">RIGHT_BRACE</span>) &amp;&amp; !<span class="i">isAtEnd</span>()) {
      <span class="i">statements</span>.<span class="i">add</span>(<span class="i">declaration</span>());
    }

    <span class="i">consume</span>(<span class="i">RIGHT_BRACE</span>, <span class="s">&quot;Expect &#39;}&#39; after block.&quot;</span>);
    <span class="k">return</span> <span class="i">statements</span>;
  }
</pre></div>
<div class="source-file-narrow"><em>lox/Parser.java</em>, add after <em>expressionStatement</em>()</div>

<p>We <span name="list">create</span> an empty list and then parse statements and
add them to the list until we reach the end of the block, marked by the closing
<code>}</code>. Note that the loop also has an explicit check for <code>isAtEnd()</code>. We have to
be careful to avoid infinite loops, even when parsing invalid code. If the user
forgot a closing <code>}</code>, the parser needs to not get stuck.</p>
<aside name="list">
<p>Having <code>block()</code> return the raw list of statements and leaving it to
<code>statement()</code> to wrap the list in a Stmt.Block looks a little odd. I did it that
way because we&rsquo;ll reuse <code>block()</code> later for parsing function bodies and we don&rsquo;t
want that body wrapped in a Stmt.Block.</p>
</aside>
<p>That&rsquo;s it for syntax. For semantics, we add another visit method to Interpreter.</p>
<div class="codehilite"><div class="source-file"><em>lox/Interpreter.java</em><br>
add after <em>execute</em>()</div>
<pre>
  <span class="a">@Override</span>
  <span class="k">public</span> <span class="t">Void</span> <span class="i">visitBlockStmt</span>(<span class="t">Stmt</span>.<span class="t">Block</span> <span class="i">stmt</span>) {
    <span class="i">executeBlock</span>(<span class="i">stmt</span>.<span class="i">statements</span>, <span class="k">new</span> <span class="t">Environment</span>(<span class="i">environment</span>));
    <span class="k">return</span> <span class="k">null</span>;
  }
</pre></div>
<div class="source-file-narrow"><em>lox/Interpreter.java</em>, add after <em>execute</em>()</div>

<p>To execute a block, we create a new environment for the block&rsquo;s scope and pass
it off to this other method.</p>
<div class="codehilite"><div class="source-file"><em>lox/Interpreter.java</em><br>
add after <em>execute</em>()</div>
<pre>
  <span class="t">void</span> <span class="i">executeBlock</span>(<span class="t">List</span>&lt;<span class="t">Stmt</span>&gt; <span class="i">statements</span>,
                    <span class="t">Environment</span> <span class="i">environment</span>) {
    <span class="t">Environment</span> <span class="i">previous</span> = <span class="k">this</span>.<span class="i">environment</span>;
    <span class="k">try</span> {
      <span class="k">this</span>.<span class="i">environment</span> = <span class="i">environment</span>;

      <span class="k">for</span> (<span class="t">Stmt</span> <span class="i">statement</span> : <span class="i">statements</span>) {
        <span class="i">execute</span>(<span class="i">statement</span>);
      }
    } <span class="k">finally</span> {
      <span class="k">this</span>.<span class="i">environment</span> = <span class="i">previous</span>;
    }
  }
</pre></div>
<div class="source-file-narrow"><em>lox/Interpreter.java</em>, add after <em>execute</em>()</div>

<p>This new method executes a list of statements in the context of a given <span
name="param">environment</span>. Up until now, the <code>environment</code> field in
Interpreter always pointed to the same environment<span class="em">&mdash;</span>the global one. Now, that
field represents the <em>current</em> environment. That&rsquo;s the environment that
corresponds to the innermost scope containing the code to be executed.</p>
<p>To execute code within a given scope, this method updates the interpreter&rsquo;s
<code>environment</code> field, visits all of the statements, and then restores the
previous value. As is always good practice in Java, it restores the previous
environment using a finally clause. That way it gets restored even if an
exception is thrown.</p>
<aside name="param">
<p>Manually changing and restoring a mutable <code>environment</code> field feels inelegant.
Another classic approach is to explicitly pass the environment as a parameter to
each visit method. To &ldquo;change&rdquo; the environment, you pass a different one as you
recurse down the tree. You don&rsquo;t have to restore the old one, since the new one
lives on the Java stack and is implicitly discarded when the interpreter returns
from the block&rsquo;s visit method.</p>
<p>I considered that for jlox, but it&rsquo;s kind of tedious and verbose adding an
environment parameter to every single visit method. To keep the book a little
simpler, I went with the mutable field.</p>
</aside>
<p>Surprisingly, that&rsquo;s all we need to do in order to fully support local
variables, nesting, and shadowing. Go ahead and try this out:</p>
<div class="codehilite"><pre>
<span class="k">var</span> <span class="i">a</span> = <span class="s">&quot;global a&quot;</span>;
<span class="k">var</span> <span class="i">b</span> = <span class="s">&quot;global b&quot;</span>;
<span class="k">var</span> <span class="i">c</span> = <span class="s">&quot;global c&quot;</span>;
{
  <span class="k">var</span> <span class="i">a</span> = <span class="s">&quot;outer a&quot;</span>;
  <span class="k">var</span> <span class="i">b</span> = <span class="s">&quot;outer b&quot;</span>;
  {
    <span class="k">var</span> <span class="i">a</span> = <span class="s">&quot;inner a&quot;</span>;
    <span class="k">print</span> <span class="i">a</span>;
    <span class="k">print</span> <span class="i">b</span>;
    <span class="k">print</span> <span class="i">c</span>;
  }
  <span class="k">print</span> <span class="i">a</span>;
  <span class="k">print</span> <span class="i">b</span>;
  <span class="k">print</span> <span class="i">c</span>;
}
<span class="k">print</span> <span class="i">a</span>;
<span class="k">print</span> <span class="i">b</span>;
<span class="k">print</span> <span class="i">c</span>;
</pre></div>
<p>Our little interpreter can remember things now. We are inching closer to
something resembling a full-featured programming language.</p>
<div class="challenges">
<h2><a href="#challenges" name="challenges">Challenges</a></h2>
<ol>
<li>
<p>The REPL no longer supports entering a single expression and automatically
printing its result value. That&rsquo;s a drag. Add support to the REPL to let
users type in both statements and expressions. If they enter a statement,
execute it. If they enter an expression, evaluate it and display the result
value.</p>
</li>
<li>
<p>Maybe you want Lox to be a little more explicit about variable
initialization. Instead of implicitly initializing variables to <code>nil</code>, make
it a runtime error to access a variable that has not been initialized or
assigned to, as in:</p>
<div class="codehilite"><pre>
<span class="c">// No initializers.</span>
<span class="k">var</span> <span class="i">a</span>;
<span class="k">var</span> <span class="i">b</span>;

<span class="i">a</span> = <span class="s">&quot;assigned&quot;</span>;
<span class="k">print</span> <span class="i">a</span>; <span class="c">// OK, was assigned first.</span>

<span class="k">print</span> <span class="i">b</span>; <span class="c">// Error!</span>
</pre></div>
</li>
<li>
<p>What does the following program do?</p>
<div class="codehilite"><pre>
<span class="k">var</span> <span class="i">a</span> = <span class="n">1</span>;
{
  <span class="k">var</span> <span class="i">a</span> = <span class="i">a</span> + <span class="n">2</span>;
  <span class="k">print</span> <span class="i">a</span>;
}
</pre></div>
<p>What did you <em>expect</em> it to do? Is it what you think it should do? What
does analogous code in other languages you are familiar with do? What do
you think users will expect this to do?</p>
</li>
</ol>
</div>
<div class="design-note">
<h2><a href="#design-note" name="design-note">Design Note: Implicit Variable Declaration</a></h2>
<p>Lox has distinct syntax for declaring a new variable and assigning to an
existing one. Some languages collapse those to only assignment syntax. Assigning
to a non-existent variable automatically brings it into being. This is called
<strong>implicit variable declaration</strong> and exists in Python, Ruby, and CoffeeScript,
among others. JavaScript has an explicit syntax to declare variables, but can
also create new variables on assignment. Visual Basic has <a href="https://msdn.microsoft.com/en-us/library/xe53dz5w(v=vs.100).aspx">an option to enable
or disable implicit variables</a>.</p>
<p>When the same syntax can assign or create a variable, each language must decide
what happens when it isn&rsquo;t clear about which behavior the user intends. In
particular, each language must choose how implicit declaration interacts with
shadowing, and which scope an implicitly declared variable goes into.</p>
<ul>
<li>
<p>In Python, assignment always creates a variable in the current function&rsquo;s
scope, even if there is a variable with the same name declared outside of
the function.</p>
</li>
<li>
<p>Ruby avoids some ambiguity by having different naming rules for local and
global variables. However, blocks (which are more like closures than like
&ldquo;blocks&rdquo; in C) in Ruby have their own scope, so it still has the problem.
Assignment in Ruby assigns to an existing variable outside of the current
block if there is one with the same name. Otherwise, it creates a new
variable in the current block&rsquo;s scope.</p>
</li>
<li>
<p>CoffeeScript, which takes after Ruby in many ways, is similar. It explicitly
disallows shadowing by saying that assignment always assigns to a variable
in an outer scope if there is one, all the way up to the outermost global
scope. Otherwise, it creates the variable in the current function scope.</p>
</li>
<li>
<p>In JavaScript, assignment modifies an existing variable in any enclosing
scope, if found. If not, it implicitly creates a new variable in the
<em>global</em> scope.</p>
</li>
</ul>
<p>The main advantage to implicit declaration is simplicity. There&rsquo;s less syntax
and no &ldquo;declaration&rdquo; concept to learn. Users can just start assigning stuff and
the language figures it out.</p>
<p>Older statically-typed languages like C benefit from explicit declaration
because they give the user a place to tell the compiler what type each variable
has and how much storage to allocate for it. In a dynamically-typed,
garbage-collected language, that isn&rsquo;t really necessary, so you can get away
with making declarations implicit. It feels a little more &ldquo;scripty&rdquo;, more &ldquo;you
know what I mean&rdquo;.</p>
<p>But is that a good idea? Implicit declaration has some problems.</p>
<ul>
<li>
<p>A user may intend to assign to an existing variable, but may have misspelled
it. The interpreter doesn&rsquo;t know that, so it goes ahead and silently creates
some new variable and the variable the user wanted to assign to still has
its old value. This is particularly heinous in JavaScript where a typo will
create a <em>global</em> variable, which may in turn interfere with other code.</p>
</li>
<li>
<p>JS, Ruby, and CoffeeScript use the presence of an existing variable with the
same name<span class="em">&mdash;</span>even in an outer scope<span class="em">&mdash;</span>to determine whether or not an
assignment creates a new variable or assigns to an existing one. That means
adding a new variable in a surrounding scope can change the meaning of
existing code. What was once a local variable may silently turn into an
assignment to that new outer variable.</p>
</li>
<li>
<p>In Python, you may <em>want</em> to assign to some variable outside of the current
function instead of creating a new variable in the current one, but you
can&rsquo;t.</p>
</li>
</ul>
<p>Over time, the languages I know with implicit variable declaration ended up
adding more features and complexity to deal with these problems.</p>
<ul>
<li>
<p>Implicit declaration of global variables in JavaScript is universally
considered a mistake today. &ldquo;Strict mode&rdquo; disables it and makes it a compile
error.</p>
</li>
<li>
<p>Python added a <code>global</code> statement to let you explicitly assign to a global
variable from within a function. Later, as a functional programming style
and nested functions became more popular, they added a similar <code>nonlocal</code>
statement to assign to variables in enclosing functions.</p>
</li>
<li>
<p>Ruby extended its block syntax to allow declaring certain variables to be
explicitly local to the block even if the same name exists in an outer
scope.</p>
</li>
</ul>
<p>Given those, I think the simplicity argument is mostly lost. There is an
argument that implicit declaration is the right <em>default</em> but I personally find
that less compelling.</p>
<p>My opinion is that implicit declaration made sense in years past when most
scripting languages were heavily imperative and code was pretty flat. As
programmers got more comfortable with deep nesting, functional programming, and
closures, it&rsquo;s become much more common to want access to variables in outer
scopes. That makes it more likely that users will run into the tricky cases
where it&rsquo;s not clear whether they intend their assignment to create a new
variable or reuse a surrounding one.</p>
<p>So I prefer explicitly declaring variables, which is why Lox requires it.</p>
</div>

<footer>
<a href="control-flow.html" class="next">
  Next Chapter: &ldquo;Control Flow&rdquo; &rarr;
</a>
Handcrafted by Robert Nystrom&ensp;&mdash;&ensp;<a href="https://github.com/munificent/craftinginterpreters/blob/master/LICENSE" target="_blank">&copy; 2015&hairsp;&ndash;&hairsp;2020</a>
</footer>
</article>

</div>
</body>
</html>
